package alogrithm.solution;

import alogrithm.structure.TreeNode;

/*
 * 求二叉树中节点的最大距离...
如果我们把二叉树看成一个图，
父子节点之间的连线看成是双向的，
我们姑且定义"距离"为两节点之间边的个数。
写一个程序，
求一棵二叉树中相距最远的两个节点之间的距离
 */
public class P11 {
	public static int getTreeHeight(TreeNode node)
	{
		if(node==null)return -1;
		return Math.max(getTreeHeight(node.getLeftChild()), getTreeHeight(node.getRightChild()))+1;
	}
	
	public static int getLongestPath(TreeNode root)
	{
		if(root==null)return 0;
		int leftResult=getLongestPath(root.getLeftChild());
		int rightResult=getLongestPath(root.getRightChild());
		int recursiveResult=Math.max(leftResult,rightResult);
		return Math.max(recursiveResult,getTreeHeight(root.getLeftChild())+getTreeHeight(root.getRightChild())+2);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TreeNode n1=new TreeNode(4);
		TreeNode n2=new TreeNode(8);
		TreeNode n3=new TreeNode(12);
		TreeNode n4=new TreeNode(16);
		TreeNode n5=new TreeNode(6,null,null);
		TreeNode n6=new TreeNode(14,n3,n4);
		TreeNode n7=new TreeNode(10,n5,n6);
		System.out.println(getLongestPath(n7));

	}

}
